package leetcode.D400.T380;

import java.util.*;

class RandomizedSet {

//    private List<Integer> array;
//    private Map<Integer, Integer> map;
//    Random random;
//
//    /** Initialize your data structure here. */
//    public RandomizedSet() {
//        array = new ArrayList<>();
//        map = new HashMap<>();
//        random = new Random();
//    }
//
//    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
//    public boolean insert(int val) {
//        if(map.containsKey(val)) return false;
//        array.add(val);
//        map.put(val, array.size()-1);
//        return true;
//    }
//
//    /** Removes a value from the set. Returns true if the set contained the specified element. */
//    public boolean remove(int val) {
//        if(!map.containsKey(val)) return false;
//        int tail = array.get(array.size()-1);
//        int idx = map.get(val);
//        array.set(idx, tail);
//        map.put(tail, idx);
//        map.remove(val);
//        array.remove(array.size()-1);
//        return true;
//    }
//
//    /** Get a random element from the set. */
//    public int getRandom() {
//        return array.get(random.nextInt(array.size()));
//    }

    // 二刷
    /*private List<Integer> array;
    private Map<Integer, Integer> map;
    private Random random;

    *//** Initialize your data structure here. *//*
    public RandomizedSet() {
        array = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();
    }

    *//** Inserts a value to the set. Returns true if the set did not already contain the specified element. *//*
    public boolean insert(int val) {
        if(map.containsKey(val)) {
            return false;
        }
        map.put(val, array.size());
        array.add(val);
        return true;
    }

    *//** Removes a value from the set. Returns true if the set contained the specified element. *//*
    public boolean remove(int val) {
        if(!map.containsKey(val)) {
            return false;
        }
        int tailVal = array.get(array.size()-1);
        int pos = map.get(val);
        array.set(pos, tailVal);
        array.remove(array.size()-1);
        map.put(tailVal, pos);
        map.remove(val);
        return true;
    }

    *//** Get a random element from the set. *//*
    public int getRandom() {
        return array.get(random.nextInt(array.size()));
    }*/

    // 三刷
    private List<Integer> list;
    private Random random;
    private Map<Integer, Integer> map;

    public RandomizedSet() {
        list = new ArrayList<>();
        random = new Random();
        map = new HashMap<>();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        map.put(val, list.size());
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int index = map.get(val);
        int last = list.get(list.size()-1);
        list.set(index, last);
        list.remove(list.size()-1);
        map.put(last, index);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */